Stemple [A]

Limit pamięci: 32 MB

Mały Jaś bawi się swoim małym magicznym stempelkiem, próbując narysować króliczka na kartce rozmiaru na , podzielonej na kwadraciki o boku . Stempelek Jasia ma kształt kwadratu o boku i składa się z mniejszych kwadratów o boku 1. Dokładnie dwa spośród tych kwadratów są wypukłe (tzn. wystające). Co więcej, oba wystające kwadraty znajdują się bądź w tym samym wierszu, bądź kolumnie. Chcąc przy użyciu stempla rysować obrazki, należy przyłożyć go do kartki, tak aby jego wystające kwadraciki trafiły dokładnie w kwadraciki na kartce. Kiedy jakiś wystający kwadracik dotknie kartki, to dotknięty kwadracik na kartce zmienia kolor - z czarnego na biały lub z białego na czarny. Przy przyłożeniu mały stempel może wystawać poza kartkę, ważne aby wystające kwadraciki znalazły się nad kartką. Stempel można przesuwać, ale nie można go obracać.

Początkowo cała kartka jest biała. Króliczek składa się z pewnej liczby kwadracików, które mają być czarne (wszystkie pozostałe kwadraciki muszą być białe). Jaś długo próbował przy pomocy swojego małego stempelka narysować króliczka, ale mu się to nie udawało (nie musi to jednak oznaczać, że jest to niemożliwe, a jedynie że małym stempelkiem ciężko jest ogarnąć taką dużą kartkę!). Poprosił więc o pomoc swojego większego brata, dużego Janka.

Duży Janek może pomóc małemu Jasiowi, dając mu duży magiczny stempel. Duży stempel ma rozmiar na i znajduje się na nim dowolna liczba wystających kwadracików (nie muszą one leżeć tylko w jednym wierszu czy też kolumnie). Stempel ten działa tak samo jak mały stempel Jasia, z jednym dodatkowym ograniczeniem - duży stempel można przystawiać tylko tak, aby w całości znajdował się nad kartką.

Zanim duży Janek da małemu Jasiowi duży stempel, chce upewnić się, że oba stemple naraz wystarczą już do narysowania króliczka. Prosi Cię więc o pomoc.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita () oznaczająca liczbę zestawów testowych. Opis jednego zestawu rozpoczyna się wierszem z dwiema liczbami całkowitymi oraz (, ), oddzielonymi pojedynczym odstępem. Oznaczają one odpowiednio rozmiar stempla dużego Jana oraz rozmiar kartki. Kolejne trzy wiersze zawierają opis stempelka małego Jasia. Każdy z tych wierszy zawiera ciąg trzech znaków 0 lub 1. Opis taki przedstawia wygląd białej kartki, do której przyłożono stempelek: 0~oznacza białe pole, zaś 1 - pole czarne. Dokładnie dwa znaki w tych trzech wierszach są jedynkami i oba znajdują się bądź w tym samym wierszu, bądź kolumnie. Zauważ, że nie jest to wygląd samego stempla - wygląd stempla jest symetrycznym odbiciem figury, którą rysuje on na kartce.

W kolejnych wierszach znajduje się opis stempla dużego Janka w analogicznym formacie, przy czym opis ten może zawierać dowolną liczbę jedynek.

Kolejne wierszy zawiera opis króliczka do narysowania, w takiej samej postaci jak opisy stempli. Jedynka oznacza, że odpowiedni kwadracik kartki powinien być zamalowany, a zero, że kartka w tym miejscu musi być biała.

Wyjście

Dla każdego zestawu testowego na standardowe wyjście wypisz jeden wiersz ze słowem TAK lub NIE, w zależności od tego, czy przy użyciu łącznie obydwu stempli da się narysować podanego w zestawie króliczka.

Przykład

Dla danych wejściowych:

2
3 8
010
000
010
000
010
011
01100000
00100000
00010000
00001100
00011110
10111100
01111100
01111110
5 10
001
001
000
00000
10100
00001
00001
00100
0011110000
0000111000
0010011100
0111001110
1110000000
1101001000
1000001100
0110110110
0001001000
0000110000

poprawną odpowiedzią jest:

NIE
TAK

Uwaga: W danych testowych użytych do oceny programu rysunki, które próbuje narysować Jaś, mogą w żaden sposób nie przypominać króliczka.

Autor zadania: Jakub Onufry Wojtaszczyk.